#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 最大顶点数
# define MAXV 5
// 定义无穷大的值，表示不存在的边
# define INF 0x3F3F3F3F

/**
 * 图的邻接表表示
 * 
0 1 0 1 0
0 0 1 1 0
0 0 0 1 1
0 0 0 0 0
1 0 0 1 0
vertex num: 5 , edge num: 8 :
0->3->1->
1->3->2->
2->4->3->
3->
4->3->0->
说明：
每一行为一个邻接表打印，邻接表存储的信息是：
头节点->与头节点相连的边节点1->与头节点相连的边节点2->...->与头节点相连的边节点n->NULL
这里注意，一个邻接表存储的并非图中节点的连接关系，而是头节点和与其相连的所有边结点的关系
 */

// 定义边节点（边节点其实存储了边和后一个节点的信息）
typedef struct ArcNode {
    // 指向节点的索引（通过该做索引可以找到头节点)
    int adjvex;
    // 指向下一个节点
    struct ArcNode *nextarc;
} ArcNode;

// 定义头节点
typedef struct VNode {
    // 指向下一个边节点
    struct ArcNode *firstarc;
} VNode;

// 定义图的邻接表结构体
typedef struct ALGraph {
    // 顶点数和边数
    int n, e;
    // 顶点邻接表
    struct VNode adjlist[MAXV];
} ALGraph;  // 这是一种定义加声明的写法

/** 
 * 使用二维数组生成一个图
 * @param graph 图的结构体指针
 * @param A 二维数组
 * @param n 图的顶点数
 */
void createALGraph(ALGraph **graph, int A[][MAXV], int n) {
    // **graph 传入的是*graph指针的地址，相当与是对于*graph指针的址传递
    int i, j;

    // 定义一个边节点结构体指针
    ArcNode *p;
    
    /**
    说明：
    当你需要在程序的多个部分使用同一个结构体实例，或者在运行时才知道需要多少个结构体实例时，
    你可以使用 malloc、calloc、realloc 等函数在堆上动态分配内存。这种情况下，分配内存是必需的。
    */
    // 动态分配内存
    *graph = (ALGraph *)malloc(sizeof(ALGraph));
    if(*graph == NULL) {
        // 内存不足时有可能造成内存分配失败
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }

    // 初始化图
    (*graph)->n = n;
    (*graph)->e = 0;
    for(int i = 0; i < n; i++) {
        (*graph)->adjlist[i].firstarc = NULL;
    }

    // 添加图中的信息
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // A[i][j]表示i和j之间的边的权值，其实代表了一条边
            if (A[i][j] != 0 && A[i][j] != INF) {
                // 创建一个边节点
                p = (ArcNode *)malloc(sizeof(ArcNode));
                if (p == NULL) {
                    fprintf(stderr, "malloc error\n");
                    exit(1);
                }
                p->adjvex = j;
                // 把前一个firstarc链接到当前边节点的nextarc，然后把当前创建的边节点再链接到头节点上
                p->nextarc = (*graph)->adjlist[i].firstarc;    // 找到边指向的节点信息，然后找到节点的下一个边节点

                // 将边节点信息链接到头节点上
                (*graph)->adjlist[i].firstarc = p;
                (*graph)->e++; // 边的数量+1
            }
        }
    }
}


void DFS(ALGraph *graph, int v, int visited[]) {
    ArcNode *p;

    if (v < MAXV) {
        visited[v] = 1;
        printf("%d ", v);
    } else {
        fprintf(stderr, "invalid agrument v: %d\n", v);
        exit(1);
    }
    p = graph->adjlist[v].firstarc;
    while (p != NULL) {
        if (visited[p->adjvex] == 0) {
            DFS(graph, p->adjvex, visited);
        }
        p = p->nextarc;
    }
}

void BFS(ALGraph *graph, int v) {
    ArcNode *p;
    // 定义队列
    int queue[MAXV], front = 0, rear = 0;
    // 出队元素索引
    int outAdjvex;
    // 定义访问标记数组
    int visited[MAXV];
    memset(visited, 0, sizeof(visited));

    // 访问第一个元素
    visited[v] = 1;
    printf("%2d ", v);

    // 将第一个元素入队
    queue[rear] = v;
    rear = (rear + 1) % MAXV;

    while (front != rear) {
        // 出队
        outAdjvex = queue[front];
        front = (front + 1) % MAXV;
        p = graph->adjlist[outAdjvex].firstarc;
        while (p != NULL) {
            if (visited[p->adjvex] == 0) {
                visited[p->adjvex] = 1;
                printf("%2d ", p->adjvex);
                // 入队
                queue[rear] = p->adjvex;
                rear = (rear + 1) % MAXV;
            }
            p = p->nextarc;
        }
    }
}


void printALGraph(ALGraph *graph) {
    int i;
    ArcNode *p;
    printf("vertex num: %d , edge num: %d :\n", graph->n, graph->e);
    for (i = 0; i < graph->n; i++) {
        printf("%d->", i);
        p = graph->adjlist[i].firstarc;
        while (p != NULL) {
            printf("%d->", p->adjvex);
            p=p->nextarc;
        }
        printf("\n");
    }
}

void destroyALGraph(ALGraph *graph) {
    int i;
    ArcNode *p, *q;
    for (i = 0; i < graph->n; i++) {
        p = graph->adjlist[i].firstarc;
        while (p != NULL) {
            q = p->nextarc;
            free(p);
            p = q;
        }
    }
    free(graph);
}


int main() {
    int i, j;
    // 有向图
    // int adjMatrix[5][5] = {
    //     { 0, 1, 0, 1, 0 },
    //     { 0, 0, 1, 1, 0 },
    //     { 0, 0, 0, 1, 1 },
    //     { 0, 0, 0, 0, 0 },
    //     { 1, 0, 0, 1, 0 },
    // }; // 声明一个5x5的邻接矩阵
    // 无向图
    int adjMatrix[5][5] = {
        { 0, 1, 0, 1, 1 },
        { 1, 0, 1, 1, 0 },
        { 0, 1, 0, 1, 1 },
        { 1, 1, 1, 0, 1 },
        { 1, 0, 1, 1, 0 },
    }; // 声明一个5x5的邻接矩阵
    // 打印邻接矩阵
    printf("5x5 :\n");
    for(i = 0; i < MAXV; i++) {
        for(j = 0; j < MAXV; j++) {
            printf("%d ", adjMatrix[i][j]);
        }
        printf("\n");
    }

    // 初始化为指针，在函数中动态分配内存
    ALGraph *graph = NULL;
    createALGraph(&graph, adjMatrix, 5);
    printALGraph(graph);

    // 深度优先遍历
    int visited[MAXV] = {0};
    printf("=======start dfs========\n");
    DFS(graph, 0, visited);
    printf("\n=======end dfs========\n");

    printf("=======start bfs========\n");
    BFS(graph, 0);
    printf("\n=======end bfs========\n");

    destroyALGraph(graph);

    return 0;
}